package leetcode.code0315;

import java.util.ArrayList;
import java.util.List;

public class Solution extends Solution315 {
	// 算法中会去查1，线段树代表从1开始，所以原始数最小也得映射成2
	// 从右侧开始出现-10000，[2,20002]上每一个数都+1。这样比-10000大的数，去查的时候都会计算这个-10000的数量
	// 所以每个数在查比`自己`小的元素，实际上去找大于等于`自己-1`的元素数量
	// 所以会去查1，-10000不映射成2， 查0就越界
	private static final int N = (int) 1e4; // 原始最大值，最大会出现10000,[-10000,10000] -> [2,20002]
	private static final int offset = N + 2; // 算法中数值的偏移量 [-1e4,1e4] ->[2,2*1e4+2]
	private static final int offset1 = N + 1; // 数值偏移量-1 [-1e4,1e4] ->[1,2*1e4+1]
	private static final int N1 = offset + N; // 算法中最大值
	private static final int Len = (N1 + 1) << 2; // 数组长度
	private int[] sum; // 数量
	private int[] cache; // 缓存 2

	@Override
	public List<Integer> countSmaller(int[] nums) {
		int size = nums.length;
		List<Integer> ans = new ArrayList<>(0);
		this.sum = new int[Len];
		this.cache = new int[Len];
		for (int i = size - 1; i >= 0; i--) {
			int num = nums[i];// nums[i] 右侧小于 num 的元素的数量。
			ans.add(0, this.query(num));// 查询小于num的数量
			this.add(num);// num添加到sum中
		}
		return ans;
	}

	private void add(int num) {
		int algNum = this.algNum(num);
		this.add(algNum, 1, N1, 1);// 从algNum到最大值NN上都+1，这样在
	}

	private void add(int l, int L, int R, int root) {
		if (l <= L && R <= N1) {// 代表 1
			this.sum[root] += R - L + 1;
			this.cache[root] += 1;
			return;
		}
		int mid = ((R - L) >> 1) + L;
		pushDown(mid - L + 1, R - mid, root);// 3
		int LRoot = root << 1;
		int RRoot = LRoot | 1;
		if (l <= mid) {
			this.add(l, L, mid, LRoot);
		}
		if (N1 > mid) {
			this.add(l, mid + 1, R, RRoot);
		}
		this.sum[root] = this.sum[LRoot] + this.sum[RRoot];
	}

	private void pushDown(int ln, int rn, int root) {
		int num = 0;
		if ((num = this.cache[root]) != 0) {
			this.sum[root << 1] += num * ln;
			this.cache[root << 1] += num;
			this.sum[root << 1 | 1] += num * rn;
			this.cache[root << 1 | 1] += num;
			this.cache[root] = 0;// 4
		}
	}

	private Integer query(int num) {
		int findNum = this.findNum(num);
		int ans = this.query(findNum, 1, N1, 1);
		return ans;
	}

	private int query(int l, int L, int R, int root) {
		if (l <= L && R <= l) {
			return this.sum[root];
		}
		int mid = ((R - L) >> 1) + L;
		pushDown(mid - L + 1, R - mid, root);
		int LRoot = root << 1;
		int RRoot = LRoot | 1;
		if (l <= mid) {
			return this.query(l, L, mid, LRoot);
		}
		if (l > mid) {
			return this.query(l, mid + 1, R, RRoot);
		}
		return 0;
	}

	// 实际数值对应在算法中的数值
	private int algNum(int num) {
		return num + offset;
	}

	// 实际要找的值，在ans中的位置， 如：右侧比2小的数量，等价于找小于等于1的数量。（算法中的数值）
	private int findNum(int num) {
		return num + offset1;// offerset - 1
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
